COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00006 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source
.turn on "→"
CS206∂(30)FINAL EXAMINATION→FALL 1976

	This examination is open book and notes.
Write LISP functions as follows except where something else is
requested.  Either notation may be used.

1. %2noccurl[x,u]%1 is the number of occurrences of the S-expression
⊗x in the list ⊗u (at the top level).

Example: %2noccurl[%1(A) , ((A) B ((A)) (A) A)] = 2.

2. %2noccurs[x,y]%1 is the number of occurrences of the S-expression
⊗x in the S-expression ⊗y (anywhere).

Example: %2noccurs%1[(A) , ((A) B ((A)) (A) A)] = 4.

3. %2samefringe[x,y]%1 is true if ⊗x and ⊗y have the same atoms
in the same order.  Thus

	%2samefringe[%1((A.B).C) , (A.(B.C))].

Write ⊗samefringe without flattening the lists ⊗x and ⊗y. 

4. We define

	%2prina[e,l] ← qif qat e qthen e . l qelse %1LP . %2prina[qa e,
%1DOT%2 . prina[qd e, %1RP%2 . l]]%1.

so that

	%2prina%1[(PLUS (TIMES A B) C),NIL] = (LP PLUS DOT LP LP TIMES
DOT LP A DOT LP B DOT NIL RP RP RP DOT LP C DOT NIL RP RP RP),

i.e. ⊗prina "prints" an S-expression in "dot" notation.

On the other hand

	%2prinb%1[(PLUS (TIMES A B) C)] = (LP PLUS LP TIMES A B RP C RP),

i.e. ⊗prinb "prints" an S-expression in "list" notation.

Hint: The second argument in each case is a list of the items to follow
the "printout" of the first expression.  It is there to make the
recursion work.

5. We have 

	%2drop u ← qif qn u qthen qNIL qelse <qa u> . drop qd u%1.

Prove that for all lists ⊗u and ⊗v 

	%2drop[u * v] = drop u * drop v%1.

6. A list structure is called compact if EQUAL subexpressions
are represented by the same list structure.  Thus
.skip 4
is a compact version of
.skip 4
and both represent the S-expression ((A) A).

	%2compact x%1 is a compact list structure EQUAL to ⊗x. 

How does the running time of your ⊗compact depend on the size of
⊗x?  How fast a version do you think can be written?  How
would it work?